#ifndef LEETCODE_CN_CPP_JIANZHI_41_H
#define LEETCODE_CN_CPP_JIANZHI_41_H

#include <queue>

using namespace std;

namespace jianzhi_41
{

class MedianFinder
{
private:
    priority_queue<int, vector<int>, greater<>> bigPart;
    priority_queue<int, vector<int>, less<>> smallPart;

public:
    MedianFinder()
    {
    }

    void addNum(int num)
    {
        if (bigPart.empty())
        {
            smallPart.emplace(num);
        }
        else if (smallPart.empty())
        {
            bigPart.emplace(num);
        }
        else
        {
            if (num >= smallPart.top())
            {
                bigPart.emplace(num);
            }
            else if (num <= bigPart.top())
            {
                smallPart.emplace(num);
            }
        }

        while (!smallPart.empty() && !bigPart.empty() && smallPart.top() > bigPart.top())
        {
            smallPart.emplace(bigPart.top());
            bigPart.pop();
        }
        while (smallPart.size() < bigPart.size())
        {
            smallPart.emplace(bigPart.top());
            bigPart.pop();
        }
        while (smallPart.size() > bigPart.size())
        {
            bigPart.emplace(smallPart.top());
            smallPart.pop();
        }
    }

    double findMedian()
    {
        if (smallPart.size() == bigPart.size())
        {
            return double(smallPart.top() + bigPart.top()) / 2.0;
        }
        return bigPart.top();
    }
};

} // namespace jianzhi_41

#endif //LEETCODE_CN_CPP_JIANZHI_41_H
